Online entities offer a wide variety of services to a variety of different client devices, including personal computers (PCs), portable digital assistants (PDAs), mobile telephones, pocket PCs, smartphones, set-top boxes, digital video recorders (DVRs), and gaming consoles, among other possibilities. These client devices often access various web services, such as online stores or other providers of audio/visual content, software programs, digital books, or other electronic content. In many cases, a request for a particular web service must be authenticated before the web service honors the request.
Some web services are configured to use software tokens to authenticate requests from client devices. In some cases, the software tokens are authenticated using encryption keys. However, these authentication schemes may require the web service to store a large number of encryption keys for validating the software tokens. For example, if each client device uses a different encryption key to access the web service, the web service may need substantial amounts of data storage capacity to store all of the encryption keys. Moreover, each time the web service receives a request with a token, the web service may use substantial processing resources to find the correct encryption key for the received token. Furthermore, the web service may have difficulty recovering from certain system failures, such as an inadvertent deletion or corruption of one or more encryption keys. Therefore, systems and methods are needed to overcome these limitations of traditional device authentication.